import java.util.*;


class Student{
    public String id;

    public Student() {
    }
    public Student(String id) {
        this.id = id;
    }

    /**
     * 注意 在传递泛型的时候，要进行重写 hashcode 和 equals
     * @param o
     * @return
     */
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                '}';
    }
}

public class Test {


    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int x:nums) {
            if(!map.containsKey(x)) {
                map.put(x,1);
            } else {
                map.put(x,map.get(x) + 1);
            }
        }
        for (int x:nums) {
            if(1 == map.get(x) ) {
                return x;
            }
        }
        return -1;
    }

    //力扣219题，是否存在重复元素   还没做完
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int ret = 0;
        int retNext = 0;
        for (int i = 0; i < nums.length; i++) {
            if(!map.containsKey(nums[i])) {
                map.put(nums[i],1);
                //ret = i;
            } else {
                map.put(i,map.get(nums[i]) + 1);
                retNext = i;
            }
            if((retNext - ret <= k)) {
                return true;
            }
        }
        return false;
    }
    //力扣219题，是否存在重复元素
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int ret = 0;
        int retNext = 0;
        for (int i = 0; i < nums.length; i++) {
            if(!map.containsKey(nums[i])) {
                map.put(nums[i],1);
                //ret = i;
            } else {
                map.put(nums[i],map.get(nums[i]) + 1);
                retNext = i;

                for (i = 0; i < retNext; i++) {
                    if(map.get(nums[i]) >= 2 && nums[i] == nums[retNext]) {
                        ret = i;
                    }
                    //这种是不对的 没考虑全面 如 1011 k=2就不行 这是右边的
                    if((retNext - ret <= k)  ) {
                        return true;
                    }
                }
                //走完这个for循环 ret就是重复元素最大的下标
            }
        }
        return false;
    }


    public static void main5(String[] args) {

        Student student1 = new Student("1234");
        System.out.println(student1.hashCode());

        Student student2 = new Student("1234");
        System.out.println(student2.hashCode());            //记得要重写equals 和 hashCode 方法，不然相同的id得到的hash值不一样
    }


    public static void main(String[] args) {
//        HashBuck hashBuck = new HashBuck();
//        hashBuck.put(1,11);
//        hashBuck.put(4,22);
//        hashBuck.put(5,55);
//        hashBuck.put(8,88);
//        hashBuck.put(3,33);
//        hashBuck.put(14,144);
//        hashBuck.put(6,66);
//        hashBuck.put(7,77);
//        hashBuck.put(2,65);
//        Integer val = hashBuck.get(4);
//        System.out.println(val);

        int[] nums = {1,2,3,1,2,3};
        int k = 2;
        boolean ret = containsNearbyDuplicate2(nums, k);
        System.out.println(ret);
    }


    public static void main1(String[] args) {
        //用于统计重复数据和其出现的次数        去重用set Set中只存储了Key   ，统计重复次数 k- v 模型用map
        int[] array = new int[] {1,2,2,3,4,4,5,6};
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int x: array) {
            if(hashMap.get(x) == null) {
                hashMap.put(x,1);
            } else {
                int val = hashMap.get(x);
                hashMap.put(x,val + 1);
            }
        }

        for (Map.Entry <Integer,Integer> entry: hashMap.entrySet()) {
            if(entry.getValue() >= 2) {
                System.out.println("key: " + entry.getKey() + "val: " + entry.getValue());
            }
        }
    }


    /**
     * 定义一个内部类
     */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /**
     *  之前百度考的一个笔试题，力扣 NO.138
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        //遍历这个链表,把现节点和新创建的节点放在hash表中，形成对应关系
        while(cur != null) {
            Node node = new Node(cur.val);   //定义多个节点，保持跟原链表一样的长度
            map.put(cur,node);
            cur = cur.next;
        }
        //再次遍历链表，给新链表 串起来
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }

    //力扣：NO771.宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        //放字符，题目上说都是不重复唯一的
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        for (int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    //牛客20题
    public static void func(String str1,String str2) {
        Set<Character> set = new HashSet<>();
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        for (int i = 0; i < str2.toCharArray().length; i++) {
            set.add(str2.charAt(i));
        }

        Set<Character> set2 = new HashSet<>();
        //再次遍历
        for (int i = 0; i < str1.toCharArray().length; i++) {
            if(!set.contains(str1.charAt(i))) {
                char ch = str1.charAt(i);
                System.out.println(ch);
            }
        }
    }
    public static void func2(String str1,String str2) {
        Set<Character> set = new HashSet<>();
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        for (int i = 0; i < str2.length(); i++) {
            set.add(str2.charAt(i));
        }

        Set<Character> set2 = new HashSet<>();
        //再次遍历
        for (int i = 0; i < str1.length(); i++) {
            if(!set.contains(str1.charAt(i)) && !set2.contains(str1.charAt(i))) {
                char ch = str1.charAt(i);
                set2.add(ch);
                System.out.println(ch);
            }
        }
    }

//    public List<String> topKFrequent(String[] words, int k) {
//
//    }



    //力扣692.前k个高频单词(中等题目)  用peek
    public List<String> topKFrequent2(String[] words, int k) {
        //1、遍历数组 统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s,hashMap.getOrDefault(s,0) + 1);
        }

        //2.相当于求前k大的，要建立小根堆
        /**
         *   注意这里我们要进行比较的是Map.Entry<String,Integer>中的次数进行比较，
         *   所以我们要传入一个比较器
         */
        Queue<Map.Entry<String,Integer>> minHeap = new PriorityQueue(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果次数相等的话，则进行比较字母前后，也就相当于建了一个大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });


        //遍历hashMap
        for (Map.Entry<String, Integer> entry: hashMap.entrySet()) {
            /**
             * 特别注意，这里是<k   而不是小于等于，因为size = 0的时候就执行了一次offer了
             */
            if (minHeap.size() < k) {
                minHeap.offer(entry);   //放入了前k个元素
            } else {
                //Map.Entry<String, Integer> top = minHeap.peek();
                //如果堆顶元素次数小于遍历的，则进行替换
                if(minHeap.peek().getValue().compareTo(entry.getValue()) < 0 ) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //这是次数相同的情况下，进行比较单词
                    //Map.Entry<String, Integer> top = minHeap.peek();
                    if (minHeap.peek().getValue().compareTo(entry.getValue()) == 0) {
                        if(minHeap.peek().getKey().compareTo(entry.getKey()) > 0) {
                            //如果遍历到的单词字母靠前的话，则与堆顶元素进行替换
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //走到这之后，小根堆中已经有了元素，依次弹出到一个数组中去
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String ch = minHeap.poll().getKey();
            list.add(ch);
        }
        //注意这是小根堆进行弹出的，所以是从小到大的，要进行反转，变成从大到小的
        Collections.reverse(list);   //这是一个专门处理集合的，类似于Arrays去处理数组的
        return list;
    }
}
